An Optimized Sparse Approximate Matrix Multiply for Matrices with Decay

摘要

We present an optimized single-precision implementation of the SparseApproximate Matrix Multiply (\SpAMM{}) [M. Challacombe and N. Bock, arXiv {\bf1011.3534} (2010)], a fast algorithm for matrix-matrix multiplication formatrices with decay that achieves an $\mathcal{O} (n \log n)$ computationalcomplexity with respect to matrix dimension $n$. We find that the max norm ofthe error achieved with a \SpAMM{} tolerance below $2 \times 10^{-8}$ is lowerthan that of the single-precision {\tt SGEMM} for dense quantum chemicalmatrices, while outperforming {\tt SGEMM} with a cross-over already for smallmatrices ($n \sim 1000$). Relative to naive implementations of \SpAMM{} usingIntel's Math Kernel Library ({\tt MKL}) or AMD's Core Math Library ({\ttACML}), our optimized version is found to be significantly faster. Detailedperformance comparisons are made for quantum chemical matrices with differentlystructured sub-blocks. Finally, we discuss the potential of improved hardwareprefetch to yield 2--3x speedups.